package elementaryAlgorithm;

import com.sun.deploy.util.StringUtils;
import com.sun.jmx.remote.internal.ArrayQueue;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @author 郭辉
 * @className TODO
 * @description 297. 二叉树的序列化与反序列化
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3,null,null,4,5]
 * 输出：[1,2,3,null,null,4,5]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 * 示例 4：
 *
 * 输入：root = [1,2]
 * 输出：[1,2]
 *
 *
 * 提示：
 *
 * 树中结点数在范围 [0, 104] 内
 * -1000 <= Node.val <= 1000
 * 通过次数205,450提交次数349,491
 * @date 2023/3/15 16:43
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet297 {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            //
            String res = "";
            if (root == null){
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            String s = levelTraversal(queue, root, res);
            return s;

        }

        // Decodes your encoded data to tre
        public TreeNode deserialize(String data) {
            String[] split = data.split(",");
            if (split.length == 1 && "".equals(split[0])){
                return null;
            }
            List<List<TreeNode>> list = new ArrayList<>();
            List<TreeNode> first = new ArrayList<>(1);
            first.add(new TreeNode(Integer.valueOf(split[0])));
            list.add(first);
            int point = 2;
            int ce = 1;
            int start = 1;
            while (point < split.length){
                List<TreeNode> tem = new ArrayList<>();
                for (int i = start; i <= point; i++) {
                    tem.add(new TreeNode(Integer.valueOf(split[i])));
                }
                list.add(tem);
                start = point + 1;
                ce++;
                point = point + 2*ce;
            }
            for (int i = 0; i < list.size()-1; i++) {
                for (int j = 0; j < list.get(i).size(); j++) {
                    if (j*2< list.get(i+1).size() && list.get(i+1).get(j*2).val != -1){
                        list.get(i).get(j).left =list.get(i+1).get(j*2);
                    }
                    if (j*2< list.get(i+1).size() && list.get(i+1).get(j*2+1).val != -1){
                        list.get(i).get(j).right =list.get(i+1).get(j*2+1);
                    }
                }
            }
            return first.get(0);
        }


    //层次遍历
        public String levelTraversal( Queue<TreeNode> queue,TreeNode node,String res){
            while (!queue.isEmpty()){
                TreeNode head = queue.poll();
                if (head == null){
                    res+="-1,";
                    continue;
                }else {
                    res += head.val + ",";
                }
                queue.add(head.left);
                queue.add(head.right);
            }

            return res;
        }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node3.left = node4;
        node3.right = node5;
        node4.left = node6;
        node4.right = node7;
        Leet297 leet297 = new Leet297();
        String serialize = leet297.serialize(root);
        TreeNode deserialize = leet297.deserialize(serialize);
    }
}

